e) (25 bodov)
Ďalšou úlohou je implementácia senzoru na identifikáciu príslušníkov K-civilizácie. Príslušníci K-civilizácie majú tvar štvorca otočeného o 45 stupňov. Každým galaktickým rokom príslušník rastie a to sa deje až do doby, kedy sa rozpadne na 4 rovnaké otočené štvorce. Zaujímavý spôsob rozmnožovania, nemyslíte? Intergalaktická správa hviezdnych prístavov by v súvislosti s poslednými teroristickými útokmi zo strany K-civilizácie voči N-civilizácii (neotočené štvorce) rada v rámci bezpečnostných opatrení automaticky identifikovala a monitorovala veľké otočené štvorce.
Na prvom riadku vstupu sa nachádzajú rozmery fotky R,C (kladné celé čísla menšie ako 1000). Na ďalších R riadkoch sa nachádza samotná fotografia: na každom riadku sa nachádza práve C znakov, každý znak je 1 alebo . (bodka). Na výstup vypíšte jediné číslo: veľkosť najväčšieho otočeného štvorca na fotografii pozostávajúceho zo znakov 1. Otočený štvorec so stranou X sa rozprestiera na 2X-1 riadkoch, v prostrednom riadku je práve 2X-1 znakov. Veľkosť otočeného štvorca je počet znakov 1, ktorými je tvorený. Ak sa na vstupe nenachádza žiaden znak 1, vypíšte nulu. Toto je jedna z úloh, kde je ľahké získať čiastočné body.
Príklad:
Vstup:
6 23
111...111..........1...
111...111.....1...111..
111...11.....11..11111.
..11........111...111..
...1...............1...
......11...........11..
Výstup:
13
Vstup:
5 5
..1..
.1.1.
111..
1.1..
11111
Výstup:
1